package first.codeTop.alibaba;

/**
 * @ClassName LC169
 * @description:
 * @author: 荣燊
 * @create: 2021-10-16 13:07
 **/
public class LC169 {
    // 多数元素，摩尔投票法。时间复杂度O(n),空间复杂度O(1)
    public static void main(String[] args) {
        int[] nums = {3, 3, 4};
        System.out.println(majorityElement(nums));
    }

    public static int majorityElement(int[] nums) {
        int mor = 1;
        int temp = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (nums[i] == temp) {
                mor++;
            } else {
                mor--;
            }
            if (mor == 0) {
                temp = nums[i];
                mor++;
            }
        }
        return temp;
    }
}
